#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: title031.py 
@version:
@time: 2023/05/14
leetcode 204.计数质数

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
"""
import pdb


class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 2:
            return 0

        isPrime = [1] * n
        isPrime[0] = isPrime[1] = 0  # 0和1不是质数，先排除掉

        # 埃式筛，把不大于根号 n 的所有质数的倍数剔除

        # for i in range(2, int(n ** 0.5) + 1):
        #     if isPrime[i]:
        #         isPrime[i * i:n:i] = [0] * ((n - i * i - 1) // i + 1)
        for i in range(2, int(n ** 0.5) + 1):
            # if isPrime[i]: 判断第 i 个数是否已经被赋值为 0 ，即对之前已经排除掉的不是质数的数，不用再对它的倍数进行二次排除。
            # 注意：埃式筛要排除的是所有小于等于根号n的质数的倍数，而不是所有小于等于根号n的数的倍数！
            if isPrime[i]:
                isPrime[i * i:n:i] = [0] * ((n - i * i - 1) // i + 1)

        return sum(isPrime)


assert Solution().countPrimes(10) == 4
print("测试成功")
